#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int flag = 1;
		for (int j = 0; j < n-1-i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
	    }
	}
}

void SelectSort(int* arr, int n)
{
	int mini = 0;
	int maxi = n - 1;
	while (mini < maxi)
	{
		int begin 
	}
}

int main()
{
	int* arr= (int*)malloc(sizeof(int) * 100000);
	srand((unsigned)time(NULL));
	for (int i = 0; i < 100000; i++)
	{
		arr[i] = rand() % 100000;
	}
	int begin = clock();
	BubbleSort(arr, 100000);


	/*int arr[10] = { 1,2,3,4,5,6,10,7,9,8 };
	InsertSort(arr, 10);*/

	int end = clock();
	printf("%d\n", end - begin);
	return 0;
}